package leetcode;

import java.util.Arrays;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/17 15:19
 *
 * 载重越大 天数越小
 * k-->days(k) 单调性
 * days(k)<=D的最大days 对应k
 *
 * 最低的取值：应该是整个货物中的最大的货物重量，要不然无法运输
 * 最高的取值，整个货物的总量
 */
public class Solution1011 {

    public int shipWithinDays(int[] weights, int D) {
        int left = Arrays.stream(weights).max().getAsInt();

        int right = Arrays.stream(weights).sum();


        while (left < right){
            int mid = left + (right-left)/2;
            if(days(weights,mid)<= D){
                //同样是继续找最小的值，mid可能是问题的解
                right =  mid;
            }else{
                left = mid + 1;
            }
        }
        return  left;
    }

    /**
     *
     * @param weights 货物数组
     * @param k  当前运输量
     * @return
     */
    private int days(int[] weights, int k) {

        int cur = 0; //当前传送带上的重点
        int res = 0; //最终的结果
        for(int weight : weights){
            if(cur + weight <=k){
                cur +=weight; //继续加
            }else{
                //如果加上weight就超重了
                res++; //明天传送
                cur  = weight; //更新为当前的重点
            }
        }
        //
        //最后一天的也要加上
        res++;
        return  res;
    }


}
